package 剑指II;

import java.util.HashSet;
import java.util.Set;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-28
 **/

public class Jz005单词长度的最大乘积 {

    /**
     * 给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
     * <p>
     * 示例 1:
     * 输入: words = ["abcw","baz","foo","bar","fxyz","abcdef"]
     * 输出: 16
     * 解释: 这两个单词为 "abcw", "fxyz"。它们不包含相同字符，且长度的乘积最大。
     * 示例 2:
     * 输入: words = ["a","ab","abc","d","cd","bcd","abcd"]
     * 输出: 4
     * 解释: 这两个单词为 "ab", "cd"。
     * 示例 3:
     * 输入: words = ["a","aa","aaa","aaaa"]
     * 输出: 0
     * 解释: 不存在这样的两个单词。
     *  
     * 提示：
     * 2 <= words.length <= 1000
     * 1 <= words[i].length <= 1000
     * words[i] 仅包含小写字母
     */

    /**
     * high level code
     * 用二进制的一位表示某一个字母是否出现过，0表示没出现，1表示出现。
     * "abcd"二进制表示00000000 00000000 00000000 00001111、
     * "bc"二进制表示00000000 00000000 00000000 00000110。
     * 当两个字符串没有相同的字母时，二进制数与的结果为0。
     */
    public int maxProductGood(String[] words) {

        int[] arr = new int[words.length];

        for (int i = 0; i < words.length; i++) {
            int num = 0;
            String word = words[i];
            for (int j = 0; j < word.length(); j++) {
                // 将1左移动?位,然后放入二进制数字中
                num |= (1 << (word.charAt(j) - 'a'));
            }
            arr[i] = num;
        }

        int result = 0;
        // 每个字符串对应的数字准备完毕,开始比对
        for (int i = 0; i < words.length; i++) {
            for (int j = i + 1; j < words.length; j++) {
                if ((arr[i] & arr[j]) == 0) {
                    result = Math.max(result, words[i].length() * words[j].length());
                }
            }
        }


        return result;
    }

    // 暴力不是很好的方法Bad low level code
    public int maxProductBad(String[] words) {
        // 是两个字符串之间不包含重复字符时

        Set[] arr = new HashSet[words.length];

        for (int i = 0; i < words.length; i++) {
            String str = words[i];
            Set<Character> set = new HashSet<>();
            for (int j = 0; j < str.length(); j++) {
                set.add(str.charAt(j));
            }
            arr[i] = set;
        }

        int result = 0;
        // 直接暴力试一试
        for (int i = 0; i < words.length; i++) {
            String str = words[i];
            for (int j = i + 1; j < arr.length; j++) {
                Set<Character> set = arr[j];
                for (int j2 = 0; j2 < str.length(); j2++) {
                    if (set.contains(str.charAt(j2))) {
                        break;
                    }
                    if (j2 == str.length() - 1) {
                        result = Math.max(result, str.length() * words[j].length());
                    }
                }
            }

        }

        return result;
    }

    public static void main(String[] args) {
        Jz005单词长度的最大乘积 n = new Jz005单词长度的最大乘积();
        String[] arr = {"abcw", "baz", "foo", "bar", "xtfn", "abcdef"};
        int result = n.maxProductBad(arr);
        System.out.println(result);
    }

}
